/*!
\file AlgReverseDelete.cpp
\brief Contains implementation of AlgReverseDelete.
*/

#include"AlgReverseDelete.h"

AlgReverseDelete::AlgReverseDelete( Graph *g ):Algorithm(g){
	containerAdd();
}

AlgReverseDelete::~AlgReverseDelete(){

}

void AlgReverseDelete::run(){
	QList<int> weights;
	QList<Edge> edges;
	for( unsigned int i = 0; i < graph()->numEdges(); i++ ){
		const Edge &e = graph()->edge(i);
		edges.push_back(e);
		weights.push_back(e.label().toInt());
	}
	
	comment("Start sorting edges.");
	while( edges.size() > 0 ){
		int max = weights[0];
		int pos = 0;
		for( int i = 1; i < edges.size(); i++ ){
			if( weights[i] > max ){
				max = weights[i];
				pos = i;
			}
		}
		c().push_back( (new ContainerElement)->setEdge(edges.takeAt(pos)) );
		weights.removeAt(pos);
	}
	comment("Edges are sorted by weight in Container 0.");
	
	while( c().size() > 0 ){
		if( existsOtherPath(*c()[0]->edge()) ){
			comment( c()[0]->edge()->toString().append(" was removed. Another path between its nodes exists.") );
			graph()->removeEdge(*c()[0]->edge());
			delete c().takeAt(0);
		}else{
			comment( c()[0]->edge()->toString().append(" is the only path between its nodes and thus is not removed.") );
			delete c().takeAt(0);
		}
	}
	comment("The MST is all that remains now.");
}

bool AlgReverseDelete::existsOtherPath( const Edge &e ){
	//For each node in our container that we considered reachable
	QList<Node> reachableNodes;
	reachableNodes.push_back(e.from());
	for( int i = 0; i < reachableNodes.size(); i++ ){
		//Store this node temporarily
		const Node currentNode = reachableNodes[i];
		//For each edge in the graph
		for( int j = 0; j < graph()->numEdges(); j++ ){
			//Store this edge temporarily
			const Edge &currentEdge = graph()->edge(j);
			if( currentEdge == e )
				continue;
			
			//If this edge starts from this node
			if( currentEdge.from() == currentNode ){
				if( currentEdge.to() == e.to() )
					return true;
				
				bool alreadyContained = false;
				for( int k = 0; k < reachableNodes.size() && !alreadyContained; k++ )
					alreadyContained = currentEdge.to() == reachableNodes[k];
				if(!alreadyContained)
					reachableNodes.push_back(currentEdge.to());
			}else if( currentEdge.to() == currentNode ){
				if( currentEdge.from() == e.to() )
					return true;
				bool alreadyContained = false;
				for( int k = 0; k < reachableNodes.size() && !alreadyContained; k++ )
					alreadyContained = currentEdge.from() == reachableNodes[k];
				if(!alreadyContained)
					reachableNodes.push_back(currentEdge.from());
			}
		}
	}
	return false;
}







